﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmExamples.字符串类算法
{

    //炼码 3845 · 最长的非前缀后缀子字符串
    //给定一个长度为n的字符串s，找到一个最长的子字符串t，使得：t 既不是s 的前缀也不是s 的后缀。s 的前缀与后缀字符串内容与t一致。

    public class LongestSubstring
    {
        // 查找最长的非前缀后缀子字符串
        static string GetLongestNonPrefixSuffixSubstring(string s)
        {
            int n = s.Length;
            if (n <= 1) return ""; // 空字符串或单个字符本身没有符合条件的子字符串

            int[] pi = ComputePrefixFunction(s);
            int maxLength = 0;
            string longestSubstring = "";

            // 从pi数组的最后一个值开始检查
            for (int length = pi[n - 1]; length > 0; length = pi[length - 1])
            {
                string candidate = s.Substring(0, length);

                // 检查是否满足条件：不是整个字符串的前缀且不是整个字符串的后缀
                if (length < n / 2 && s.Substring(0, length) == s.Substring(n - length, length))
                {
                    // 检查中间部分是否存在与候选子字符串相同的子字符串
                    for (int i = length; i < n - length; i++)
                    {
                        if (s.Substring(i, length) == candidate)
                        {
                            // 更新最长满足条件的子字符串
                            if (length > maxLength)
                            {
                                maxLength = length;
                                longestSubstring = candidate;
                            }
                            break; // 找到一个满足条件的子字符串后退出循环
                        }
                    }
                }
            }

            return longestSubstring;
        }

        // 计算前缀函数（部分匹配表）
        static int[] ComputePrefixFunction(string s)
        {
            int n = s.Length;
            int[] pi = new int[n];
            int j = 0;

            for (int i = 1; i < n; i++)
            {
                while (j > 0 && s[i] != s[j])
                {
                    j = pi[j - 1];
                }

                if (s[i] == s[j])
                {
                    j++;
                }

                pi[i] = j;
            }

            return pi;
        }

        public LongestSubstring(string str)
        {
            Console.WriteLine(GetLongestNonPrefixSuffixSubstring(str)); // Output: ""
        }
    }
}
